//给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 
//endDayi 。 
//
// 你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。 
//
// 请你返回你可以参加的 最大 会议数目。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：events = [[1,2],[2,3],[3,4]]
//输出：3
//解释：你可以参加所有的三个会议。
//安排会议的一种方案如上图。
//第 1 天参加第一个会议。
//第 2 天参加第二个会议。
//第 3 天参加第三个会议。
// 
//
// 示例 2： 
//
// 
//输入：events= [[1,2],[2,3],[3,4],[1,2]]
//输出：4
// 
//
// 
//
// 提示： 
//
// 
// 1 <= events.length <= 10⁵ 
// events[i].length == 2 
// 1 <= startDayi <= endDayi <= 10⁵ 
// 
//
// Related Topics 贪心 数组 排序 堆（优先队列） 👍 320 👎 0


package LeetCode.editor.cn;


import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2025-07-07 15:57:30
 * @description 1353.最多可以参加的会议数目
 
 */
 
public class MaximumNumberOfEventsThatCanBeAttended {
    public static void main(String[] args) {
    //测试代码
    MaximumNumberOfEventsThatCanBeAttended fun = new MaximumNumberOfEventsThatCanBeAttended();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
        * 每天只能参加一场，根据贪心原则
        * 应该尽可能安排结束时间早的，因为晚的可以在后面安排
        * 枚举1~最大结束时间，每次选择该结束时间下最早结束的时间
        * 用一个最小堆来保存当前结束时间最小的会议
        * */
    public int maxEvents(int[][] events) {
        int n=events.length;
        int maxDay=0;
        //先找出最大的截至日期
        for (int[] event : events) {
            maxDay=Math.max(maxDay,event[1]);
        }
        //默认是最小堆
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        int ans=0;
        //按照开始时间先排序
        Arrays.sort(events,(a,b)->a[0]-b[0]);
        // i表示截至时间，j是所有会议的编号
        for (int i = 1,j=0; i <=maxDay; i++) {
            while (j<n&&events[j][0] <= i) {
                //如果当前的日期小于等于开始日期，加入优先队列
                //表示在当前截至时间可以安排
                pq.offer(events[j][1]);
                j++;
            }
            // 如果优先队列不为空，且队列顶部的会议结束时间小于当前日期
            //则说明该会议已经结束，不能参加
            while (!pq.isEmpty()&&pq.peek()<i) {
                pq.poll();
            }
            //如果优先队列不为空，说明有会议可以参加
            // 判断当前截至时间下可以参会的会议（即选择最小的）
            if (!pq.isEmpty()) {
                //如果优先队列不为空，说明可以参加会议
                pq.poll();
                ans++;
            }
        }
       return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
